package java学习.leetcode.editor.cn;

import com.sun.source.tree.Tree;
import 操作系统实验.实验二.生产者与消费者.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 刘世锦
 * 2023-01-09 21:06:47	 当前时间
 */
//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// nums 按 严格递增 顺序排列 
// 
// Related Topics 树 二叉搜索树 数组 分治 二叉树 
// 👍 1214 👎 0

public class 将有序数组转换为二叉搜索树{
	public static void main(String[] args) {
		Solution solution = new 将有序数组转换为二叉搜索树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/14 15:29
	 */
	public TreeNode sortedArrayToBST(int[] nums) {

		if (nums.length==0){
			return null;
		}

		return dfsByReview(nums,0,nums.length-1);



	}

	private TreeNode dfsByReview(int[] nums, int start, int end) {
		if (start>end){
			return null;
		}
		int mid = (start+end)/2;
		TreeNode node = new TreeNode(nums[mid]);
		node.left = dfsByReview(nums,start,mid-1);
		node.right = dfsByReview(nums,mid+1,end);
		return node;
	}

	// 复习end

	/**
	 *    0 1 2 3 4
	 * -10 -3 0 5 9
	 *  mid 2 0 3            0  -10-r  5
	 * -1 -1 -1   _       -1  -1 _
	 *  0  0  3   _       1  4   _
	 *  4  1  4  _       1   4   _
	 *
	 *          0             0         -1  0
	 *        /  \          /  \          /  \
	 *     -10   5        -3   9    -1 -10   -1 5
	 *       \    \       /   /           \    \
	 *       -3    9    -10  5            -1   -1
	 *
	 *
	 * @param nums
	 * @return
	 */
	public TreeNode sortedArrayToBSTDFS(int[] nums) {

		Queue<TreeNode> curNodeQueue = new LinkedList<>();
		Queue<Integer> leftRange = new LinkedList<>();
		Queue<Integer> rightRange = new LinkedList<>();
		TreeNode root = new TreeNode(-1);
		curNodeQueue.offer(root);
		leftRange.offer(0);
		rightRange.offer(nums.length-1);
		while (!curNodeQueue.isEmpty()){
			TreeNode cur = curNodeQueue.poll();
			Integer left = leftRange.poll();
			Integer right = rightRange.poll();
			int mid = left+(right-left)/2;
			cur.val = nums[mid];
			if (left<mid){
				cur.left = new TreeNode(-1);
				curNodeQueue.offer(cur.left);
				leftRange.offer(left);
				rightRange.offer(mid-1);
			}
			if (right>mid){
				cur.right = new TreeNode(-1);
				curNodeQueue.offer(cur.right);
				leftRange.offer(mid+1);
				rightRange.offer(right);
			}
		}
		return root;

	}

		public TreeNode sortedArrayToBST1(int[] nums) {

    	return dfs(nums,0,nums.length-1);

    }
    public TreeNode dfs(int[] nums,int left,int right){
    	if (left>right){
    		return null;
		}
//    	int mid = (right+left)/2;
		int mid = left+ (right-left)/2;
    	TreeNode root = new TreeNode(nums[mid]);
    	root.left = dfs(nums,left,mid-1);
    	root.right = dfs(nums,mid+1,right);
    	return root;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
